package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2021/1/18 12:45
 * @Version 1.0
 **/
public class AccountsMerge {



    public static void main(String[] args) {

    }

    static int[] f;

    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        List<List<String>> result = new ArrayList<>();
        if (null == accounts || accounts.size() < 1) {
            return result;
        }
        int size = accounts.size();
        f = new int[size];
        for (int i = 0; i < size; i++) {
            f[i] = i;
        }
        HashMap<String, HashSet<Integer>> emailToIndex = new HashMap<>();
        HashSet<Integer> indexs = null;
        String email;
//        result.add(accounts.get(0));
        for (int i = 0; i < size; i++) {
            List<String> emails = accounts.get(i);
            if (null != emails && emails.size() > 1) {
                int len = emails.size();
                for (int j = 1; j < len; j++) {
                    email= emails.get(j);
                    indexs = emailToIndex.getOrDefault(email, new HashSet<>());
                    indexs.add(i);
                    emailToIndex.put(email,indexs);
                }
            }
        }
        Set<String> keySet = emailToIndex.keySet();
        for (String key : keySet) {
            indexs = emailToIndex.get(key);
            Integer preIndex = null;
            for (Integer index : indexs) {
                if (null == preIndex) {
                    preIndex = index;
                    continue;
                }
                merge(preIndex,index);
                preIndex = index;
            }
        }

        int tag = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        HashMap<String, TreeSet<String>> nameToEmails = new HashMap<>();
        String name;
        TreeSet<String> emails;
        List<String> strings;
        int strLen;
        for (int i = 0; i < size; i++) {

            strings = accounts.get(i);
            strLen = strings.size();
            name = strings.get(0);

            f[i] = findFather(i);
            if (map.getOrDefault(f[i],-1) < 0) {
                map.put(f[i],tag++);
                emails = nameToEmails.getOrDefault(name, new TreeSet<>());
                emails.addAll(strings.subList(1,strLen));
                nameToEmails.put(name+"_"+f[i],emails);
            } else {

                emails = nameToEmails.get(name + "_" + f[i]);
                emails.addAll(strings.subList(1,strLen));
                nameToEmails.put(name+"_"+f[i],emails);
            }
        }

        nameToEmails.forEach((key,value) -> {
            ArrayList<String> strList = new ArrayList<>();
            strList.add(key.split("_")[0]);
            strList.addAll(value);
            result.add(strList);

        });
        return result;
    }

    /**
     *
     * @param preIndex
     * @param index
     * @return true 表示preIndex和index  原本就在一起 false  表示 原本是不在一起的
     */
    private static boolean merge(Integer preIndex, Integer index) {
        int fa_preIndex = findFather(preIndex);
        int fa_index = findFather(index);
        if (fa_preIndex != fa_index) {
//            fa_preIndex = findFather(fa_preIndex);
            f[fa_index] = fa_preIndex;
            return false;
        } else {
            return true;
        }
    }

    /**
     * 查找节点的父节点
     * @param fa_preIndex
     * @return
     */
    private static int findFather(int fa_preIndex) {
        if (fa_preIndex != f[fa_preIndex]) {
            fa_preIndex = findFather(f[fa_preIndex]);
        }
        return fa_preIndex;
    }
}
